给定一个序列,每次查询一个区间 中所有子序列分别去重后的和 的结果。
乍一看好像不太可做,仔细分析发现有点规律:
在一个长度为 的序列中,一个数出现次数为 。则有 个子序列不包含该元素,它的贡献是 。
问题转化为如何快速求出每一个数的贡献值。
、离线、维护数列,想到什么?莫队!
我们使用莫队记录双向链表(建议手写),维护每个数分别的出现次数,下标表示数,内容为出现次数。则这个链表的元素个数大致在 级别。在跳到当前区间后,枚举维护的链表,对于每个元素分别算出贡献值后相加即可。
还剩下最后一个问题:如何快速求出 ?普通的快速幂可能做不到,因为带一只 ,容易被卡。果断选用光速幂。
光速幂是什么呢?就是一种 预处理、 查询的,求特定底数的幂的快速方法。具体方案是:预处理 和 ,然后根据商和余数即可 求出结果。
代码:
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5+5;
ll n, m, a[N], SIZE, cnt[N], s[N], ans[N];
#define whichBlock(x) (\
(x-1)/SIZE+1\
)
struct Query {
ll l, r, p, id;
Query(ll a=0, ll b=0, ll c=0, ll d=0) : l(a), r(b), p(c), id(d) {}
~Query() {}
friend bool operator < (const Query &a, const Query &b) {
ll x = whichBlock(a.l), y = whichBlock(b.l);
if(x == y) return a.r < b.r;
return x < y;
}
}q[N];
struct myList {
struct Node {
ll pre, nxt;
Node(ll a=0, ll b=0) : pre(a), nxt(b) {}
~Node() {}
}nd[N];
ll tot;
myList(ll a=0) : tot(a) {}
~myList() {}
void insert(ll x) {
nd[tot].nxt = x;
nd[x].pre = tot;
tot = x;
}
void erase(ll x) {
if(x != tot) {
nd[nd[x].pre].nxt = nd[x].nxt;
nd[nd[x].nxt].pre = nd[x].pre;
}
else {
nd[nd[x].pre].nxt = 0;
tot = nd[x].pre;
}
nd[x] = Node();
}
}lst;
namespace qpow {
ll pow1[N], pow2[N];
void initPow(ll mod) {
pow1[0] = pow2[0] = 1;
for(ll i=1;i<=SIZE;i++) pow1[i] = pow1[i-1] * 2 % mod;
for(ll i=1;i<=SIZE;i++) pow2[i] = pow2[i-1] * pow1[SIZE] % mod;
}
ll calc(ll x, ll mod) {return pow1[x%SIZE]*pow2[x/SIZE]%mod;}
}
void upd(ll x, ll k) {
if(!(s[cnt[a[x]]]-=a[x])) lst.erase(cnt[a[x]]);
if(!s[cnt[a[x]]+=k]) lst.insert(cnt[a[x]]);
s[cnt[a[x]]] += a[x];
}
int main() {
scanf("%lld%lld", &n, &m);
SIZE = sqrt(n);
for(ll i=1;i<=n;i++) scanf("%lld", &a[i]);
for(ll i=1;i<=m;i++) scanf("%lld%lld%lld", &q[i].l, &q[i].r, &q[i].p), q[i].id = i;
sort(q+1, q+1+m);
ll l = 1, r = 0;
for(ll i=1;i<=m;i++) {
// printf("QUERY #%d: id=%d l=%d r=%d p=%d\n", i, q[i].id, q[i].l, q[i].r, q[i].p);
qpow::initPow(q[i].p);
while(l > q[i].l) upd(--l, 1);
while(r < q[i].r) upd(++r, 1);
while(l < q[i].l) upd(l++, -1);
while(r > q[i].r) upd(r--, -1);
for(ll j=lst.nd[0].nxt;j;j=lst.nd[j].nxt) {
// printf("LIST POSITION: %d\n", j);
ll _1 = qpow::calc(r-l+1, q[i].p);
ll _2 = qpow::calc(r-l+1-j, q[i].p);
ll _3 = ((_1 - _2) * s[j] + q[i].p) % q[i].p;
ans[q[i].id] = (ans[q[i].id] + _3 + q[i].p) % q[i].p;
}
}
for(ll i=1;i<=m;i++) printf("%lld\n", ans[i]);
return 0;
}